import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;


/**
 * @program: LeetCode
 * @description: LeetCode : 剑指 Offer II 083. 没有重复元素集合的全排列
 * @author: WXY
 * @create: 2023-01-04 21:03
 * @Version 1.0
 **/
public class Num_offer2_083_permute {

    public static List<List<Integer>> permute(int[] arr) {
        if (arr == null || arr.length == 0) {
            return new ArrayList<>();
        }
        List<List<Integer>> all = new ArrayList<>();
        HashSet<Integer> use = new HashSet<>();
        ArrayList<Integer> curList = new ArrayList<>();
        //process(arr, use, curList,all);
        process1(arr, 0, all);
        return all;
    }

    private static void process(int[] arr, HashSet<Integer> use, ArrayList<Integer> curList, List<List<Integer>> all) {
        if (use.size() == arr.length) {
            all.add(new ArrayList<>(curList));
        } else {
            for (int i = 0; i < arr.length; i++) {
                if (!use.contains(i)) {
                    use.add(i);
                    curList.add(arr[i]);
                    process(arr, use, curList, all);
                    curList.remove(curList.size() - 1);
                    use.remove(i);
                }
            }
        }
    }

    private static void process1(int[] arr, int i, List<List<Integer>> all) {
        if (i == arr.length) {
            ArrayList<Integer> curList = new ArrayList<>();
            for (int num : arr) {
                curList.add(num);
            }
            all.add(curList);
        } else {
            for (int j = i; j < arr.length; j++) {
                swap(arr, i, j);
                process1(arr, i + 1, all);
                swap(arr, i, j);
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


    public static void main(String[] args) {
        int[] arr = {1, 2, 3};
        List<List<Integer>> list = permute(arr);
        System.out.println(list);

    }
}
